|
In graph drawing, a clustered planar graph is a graph together with a hierarchical clustering on its vertices, such that the graph drawn together with a collection of simple closed curves surrounding each cluster, so that there are no crossings between graph edges or clusters.〔. A brief survey paper associated with an invited talk at SCG.〕 The clustering can be described combinatorially by a collection of subsets of the vertices such that, for each two subsets, either both are disjoint or one is contained in the other. It is not required that the clustering be maximal nor that every vertex belong to a cluster. In a clustered planar drawing, no two edges may cross each other (that is, the graph must be planar), no two of the curves representing clusters may cross each other, an edge may cross a cluster boundary only if it connects a vertex inside the cluster to a vertex outside the cluster, and when an edge and cluster boundary cross they may cross only once.〔 It is unknown whether it is possible to construct clustered planar drawings in polynomial time. However, many special cases have polynomial time algorithms.〔.〕 ==Connected clusters== The clustered planarity problem was introduced by , who posed the general problem but gave a polynomial time algorithm only for the special case in which each cluster forms a connected subgraph of the input graph. Their algorithm processes the clustering hierarchy in bottom-up order, using PQ tree data structures to represent the possible orderings of the edge crossings around each cluster boundary.〔.〕 Later, observed that an earlier paper by also contained very similar results. Lengauer was primarily interested in testing planarity of graphs defined by graph rewriting schemes, but his algorithm can also be used to test clustered planarity in the connected case.〔. A preliminary version of these results was announced earlier at the 13th International Colloquium on Automata, Languages and Programming (ICALP '86), , .〕 Although the running time of Lengauer's algorithm is linear in its input size, it only gives a quadratic time algorithm for clustered planarity, because the graph rewriting description of the input can be significantly larger than the data needed to describe a clustered planarity instance.〔 claimed a linear time algorithm for connected clustered planarity, but did not provide full details;〔.〕〔 a later linear time algorithm was given by .〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Clustered planarity」の詳細全文を読む スポンサード リンク
|